package zwp.exercise.intereview.base.binary_search;

import java.util.Arrays;

/**
 * @Author zwp14
 * @create 2024/6/27 18:29
 * @description 二分查找代码
 */
public class BinarySearch {
    private static int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};

    public static void main(String[] args) {

        //定义数组


        int end = array.length - 1;

        int start = 0;
//需求,找45这个数字,采用二分查找方法
        int target = 48;

//        method1(array, end, start, target);

        int i = method2(start, end, target);
        if (i >= 0) {
            System.out.println("成功找到数字:" + array[i] + "索引为:" + i);
        } else {
            System.out.println("查询数字不在该数组当中!");
        }
    }

    /**
     * 参考博主写的二分查找
     *
     * @param start  开始索引
     * @param end    结束索引
     * @param target 目标数字
     * @return 结果
     */
    private static int method2(int start, int end, int target) {
        int count = 0;
        while (start <= end) {
            count++;
            //这里用到移位运算等价于除以2(在正数情况下),能够解决整数溢出的问题,而且效率比较高
            int half = (start + end) >>> 1;
            if (array[half] == target) {
                System.out.println("查找次数:"+count);
                return half;
            } else if (array[half] > target) {
                end = half - 1;
            } else if (array[half] < target) {
                start = half + 1;
            }
        }
        return -1;
    }

    /**
     * 自写
     *
     * @param array  数组
     * @param end    结束索引
     * @param start  开始索引
     * @param target 目标数字
     */
    private static void method1(int[] array, int end, int start, int target) {
        int count = 0;

        while (start <= end) {
            int half = (start + end) / 2;
            count++;
            if (target == array[half]) {
                System.out.print("找到正确数字!索引为:" + half);
                System.out.println("第" + count + "次查找:" + array[half]);
                break;
            } else if (target < array[half]) {
                System.out.println("第" + count + "次查找:" + array[half] +
                        "查找的数字小于中间数!舍弃中间数右边的所有数字");
                end = half - 1;
            } else if (target > array[half]) {
                System.out.println("第" + count + "次查找:" + array[half] +
                        "查找的数字大于中间数!舍弃中间数左边的所有数字");
                start = half + 1;
            } else {
                System.out.println("未查找到!");
            }
        }
    }
}
